/**
 * 
 */
package backtrack.passed2;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * @author xyyi
 *
 */
public class Subsets {

    /**
    Given a set of distinct integers, S, return all possible subsets.

    Note:

    Elements in a subset must be in non-descending order.
    The solution set must not contain duplicate subsets.
    For example,
    If S = [1,2,3], a solution is:

    [
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
    ]
     */
    public List<List<Integer>> subsetsR0(int[] S) {
        List<List<Integer>> list = new ArrayList<>();
        if (S == null)
            return list;
        List<Integer> buffer = new ArrayList<>();
        subsetsR0Helper(S, buffer, list, 0);
        return list;
    }

    public void subsetsR0Helper(int[] S, List<Integer> buffer,
            List<List<Integer>> list, int index) {
        if (index == S.length) {
            ArrayList<Integer> arr = new ArrayList<Integer>(buffer);
            Collections.sort(arr);
            list.add(arr);
        } else {
            buffer.add(S[index]);
            subsetsR0Helper(S, buffer, list, index + 1);
            buffer.remove(buffer.size() - 1);
            subsetsR0Helper(S, buffer, list, index + 1);
        }
    }

    // best for interview
    public List<List<Integer>> subsetsR(int[] S) {
        List<List<Integer>> sets = new ArrayList<>();
        List<Integer> cache = new ArrayList<>();
        
        Arrays.sort(S);
        sets.add(new ArrayList<>(cache));
        subsetsRHelper(S, 0, cache, sets);
        return sets;
    }
    
    private void subsetsRHelper(int[] S, int level, List<Integer> cache, List<List<Integer>> sets) {
        // This is optional
        if (level == S.length) {
            return;
        }
        
        for (int i = level; i < S.length; i++) {
            cache.add(S[i]);
            sets.add(new ArrayList<>(cache));
            subsetsRHelper(S, i + 1, cache, sets);
            cache.remove(cache.size() - 1);
        }
    }

    // Good for interview
    public List<List<Integer>> subsetsI(int[] S) {
        Arrays.sort(S);
        List<List<Integer>> sets = new ArrayList<>();
        sets.add(new ArrayList<Integer>());
        
        for (int i = 0; i < S.length; i++) {
            for (int j = 0, size = sets.size(); j < size; j++) {
                List<Integer> newSet = new ArrayList<>(sets.get(j));
                newSet.add(S[i]);
                sets.add(newSet);
            }
        }
        
        return sets;
    }
    
    public List<List<Integer>> subsetsBitsOpsI(int[] S) { 
        Arrays.sort(S);
        int n = S.length; 
        int K = (int) Math.pow(2, n); 
        List<List<Integer>> sets = new ArrayList<List<Integer>>(); 
        for (int i = 0; i < K; i++) { 
            int j = i;
            List<Integer> list = new ArrayList<Integer>(); 
            int index = 0; 
            while (j != 0) { 
                if (j % 2 != 0) { 
                    list.add(S[index]); 
                } 
                index++; 
                j >>= 1; 
            } 
            sets.add(list); 
        } 
        return sets; 
    }
    
 
    /**
     * Subset II

     */
    //best for interview
    public List<List<Integer>> subsetsWithDupR(int[] num) {
        List<List<Integer>> list = new ArrayList<>();
        if (num == null)
            return list;
        List<Integer> buffer = new ArrayList<Integer>();
        list.add(new ArrayList<Integer>(buffer));
        Arrays.sort(num);
        subsetsWithDupRHelper(num, buffer, list, 0);
        return list;
    }

    private void subsetsWithDupRHelper(int[] num, List<Integer> buffer,
            List<List<Integer>> list, int index) {
        for (int i = index; i < num.length; i++) {
            buffer.add(num[i]);
            list.add(new ArrayList<Integer>(buffer));
            subsetsWithDupRHelper(num, buffer, list, i + 1);
            buffer.remove(buffer.size() - 1);
            // the only difference with no duplication
            while (i < num.length - 1 && num[i] == num[i + 1])
                i++;
        }
    }
    
    // good for interview
    public List<List<Integer>> subsetsWithDupI(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> subsets = new ArrayList<>();
        subsets.add(new ArrayList<Integer>());
        
        int size = 0;
        for (int i = 0; i < num.length; i++) {
        	// start index to avoid duplication
            int start = i > 0 && num[i] == num[i - 1] ? size : 0;
            size = subsets.size();
            for (int j = start; j < size; j++) {
                List<Integer> newSet = new ArrayList<>(subsets.get(j));    
                newSet.add(num[i]);
                subsets.add(newSet);
            }
        }
        
        return subsets;
    }
    
    

    /**
     * 
     */
    public Subsets() {
        // TODO Auto-generated constructor stub
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        Subsets subSet = new Subsets();
        int[] S = new int[] { 1, 2, 2 };
        List<List<Integer>> lists = subSet.subsetsWithDupI(S);
        for (List<Integer> list : lists) {
            for (int i : list) {
                System.out.printf("%d,", i);
            }
            System.out.println();
        }
    }
}
